package chart.树的遍历;

import chart.TreeNode;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/4/13 17:06
 * 中序遍历 - 左子树 -> 根 ->右子树
 * 算法：递归   迭代
 */
public class InOrder {
    public static void main(String[] args) {
        TreeNode<Integer> root = new TreeNode(4, new TreeNode(2, new TreeNode(1, null, null), new TreeNode(3, null, null)),
                new TreeNode(6, null, null));
        inOrderRecurse(root);
        System.out.println();
        inOrderIterate(root);
    }

    /**
     * 递归
     *
     * @param node 参数
     */
    static void inOrderRecurse(TreeNode<Integer> node) {
        if (node == null) return;
        if (node.left != null) inOrderRecurse(node.left);
        System.out.print(node.val + " ");
        if (node.right != null) inOrderRecurse(node.right);
    }

    static void inOrderIterate(TreeNode<Integer> node) {
        if (node == null) return;
        Deque<TreeNode<Integer>> stack = new ArrayDeque<>();
        while (true) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            if (stack.isEmpty()) break;
            node = stack.pop();
            System.out.print(node.val + " ");
            node = node.right;
        }
    }

    static void inOrderIteratorV2(TreeNode<Integer> node) {
        Stack<TreeNode<Integer>> stack = new Stack<>();
        while (node != null || !stack.isEmpty()) {
            if (node != null) {
                stack.push(node);
                node = node.left;
            } else {
                node = stack.pop();
                System.out.print(node.val + " ");
                node = node.right;
            }
        }
        System.out.println();
    }

}







